LeetCode 1124、表现良好的最长时间段

一、题目描述

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

示例 1：

输入：hours = [9,9,6,0,6,6,9] 输出：3 解释：最长的表现良好时间段是 [9,9,6]。

示例 2：

输入：hours = [6,6,6] 输出：0

提示：

• 1 <= hours.length <= 10^4
• 0 <= hours[i] <= 16

二、题目解析

三、参考代码

// https://leetcode.cn/problems/longest-well-performing-interval/
class Solution {
    public int longestWPI(int[] hours) {
        // 记录当前子数组的长度
        // 表示 表现良好时间段 的最大长度
        int maxInterval = 0;

        // 哈希表中记录每个 非零 前缀和 的 第一次 出现的 下标
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        // preSum 表示前缀和
        // 它是一个变量，一直迭代
        int preSum = 0;

        for (int i = 0; i < hours.length; i++) {
            
            // 如果 hours > 8 
            // 则 preSum 加 1，否则 preSum 减 1
            preSum += hours[i] > 8 ? 1 : -1;

            // 如果 preSum > 0
            // 表明从数组索引为 0 的位置出发到索引为 i 的位置
            // [ 0 , i ] 区间所有元素和大于 0
            if (preSum > 0) {

                // 从数组索引为 0 的位置出发到索引为 i 的位置组成的子数组就是 表现良好时间段 
                maxInterval = i + 1;

            // 如果某一个位置的前缀和 preSum 不大于 0
            } else{

                // putIfAbsent() 方法会先判断指定的键（key）是否存在
                // 不存在则将键/值对插入到 HashMap 中
                // key 如果存在就不存储
                map.putIfAbsent(preSum, i);

                // 查找[ 0 , i ] 这个区间当中，是否已经保存了前缀和为 preSum - 1 的情况
                // 如果有这种情况，表示某个区间 [ 0 , j ] 的元素和为 preSum - 1
                if (map.containsKey(preSum - 1)) {

                    // 区间 [ 0 , j ] 的元素和为 preSum - 1
                    int j =  map.get(preSum - 1);

                    // 此时，我们访问的是索引为 i 的元素，整个区间是这样的
                    // [ 0 , ... , j , ... , i , .... ]
                    // [ 0 , i ] 区间里面的所有元素和是 preSum
                    // [ 0 , j ] 区间里面的所有元素和是 preSum - 1
                    // ( j , i ] 区间里面的所有元素和是 1 ，是 表现良好的时间段
                    int interval = i - j;

                    // 更新最值
                    maxInterval = Math.max(maxInterval, interval);

                }
            }   
        }

        // 返回结果
        return maxInterval;
    }
}